1. Field of the Invention
The present invention relates generally to cryptography and, more particularly, to the exchanging of cryptographic keys between two cryptographic units.
2. Description of the Prior Art
Two mutually-exclusive classes of cryptographic methods and protocols are well recognized by those familiar with cryptography, symmetric cryptography and public-key cryptography. In symmetric cryptographic protocols, the same key and cryptographic method are used both for encrypting a plaintext message into cyphertext, and for decrypting a cyphertext to recover the plaintext. It is readily apparent that the security of a symmetric cryptographic protocol can never exceed the security of the single key used both for encryption and decryption.
In public-key cryptographic protocols there are two keys, a public key to which anyone can gain access and which is used only for encrypting a plaintext message, and a private key which only the recipient possesses and which is used only for decrypting a cyphertext. For a public-key cryptographic protocol to be secure it must be unfeasible to determine the private key by analyzing the public key. While public-key cryptographic systems appear alluring, thus far in practice it has been observed that public-key cryptographic methods are significantly slower than symmetric cryptographic methods. In general, it has been found that public-key cryptographic methods are 1000 times slower than symmetric cryptographic methods.
Managing the distribution of cryptographic keys is the most difficult security problem in using cryptography both for symmetric protocols and for public-key protocols. Developing secure cryptographic methods and protocols is not easy, but making sure the keys used with such methods and protocols remain secret is an even more difficult task. "Cryptanalysts often attack both symmetric and public-key cryptosystems through their key management." Schneier, Applied Cryptography, .COPYRGT. 1994 John Wiley & Sons, Inc. ("Schneier") p. 140.
For symmetric cryptographic protocols, there are three well recognized key management problems. First a key may be compromised which permits an eavesdropper who obtains the key either to read all the cyphertext, or even to broadcast bogus cyphertext. The only way to alleviate this problem is to change keys frequently. A second problem for symmetric cryptography key management is that it requires a large number of keys if each pair of individuals in a group is to communicate using a different key. Forty-five unique keys are required if a group of 10 individuals are to communicate. Fifty-five unique keys are required for communication among a group of 11 individuals. The final problem for key management in symmetric cryptographic protocols is that, since keys are more valuable than the encrypted messages, the keys must be exchanged by a secure communication. One approach for securely distributing keys of a symmetric cryptographic protocol is to distribute the keys using a public-key cryptographic protocol.
Whether used with a symmetric cryptographic protocol or with a public-key cryptographic protocol, an encryption key should not be used indefinitely. First, the longer a key is used the more likely it will be compromised by theft, luck, extortion, bribery or cryptanalysis. Long use of a key aids an eavesdropper because that provides more cyphertext encoded with the same key to which cryptoanalytic methods may be applied. Second, on the average the longer a key is used the greater the loss if the key is compromised.
Schneier pp. 376-381 describes various key exchange protocols including:
1. Shamir's Three-Pass protocol; PA1 2. a COMSET protocol; and PA1 3. an Encrypted Key Exchange protocol that may be implemented with various different cryptographic methods such as:
a. a Rivest, Shamir and Adleman ("RSA") public-key cryptographic method that is described in U.S. Pat. No. 4,405,829; PA2 b. an ElGamal public-key cryptographic method; and PA2 c. a Diffie-Hellman public-key cryptographic method that is described in U.S. Pat. No. 4,200,770.
U.S. Pat. Nos. 4,405,829 and 4,200,770 together with Schneier are hereby incorporated by reference.
While all of the preceding protocols provide secure methods for establishing a key, the various protocols require exchanging several, time consuming communications between the parties to establish the key. Moreover, those protocols which require using a public-key cryptographic method also suffer from the slowness of such methods. Moreover, the preceding key exchange protocols are no more secure than the cryptographic method which they employed for key exchange.
Swifter and simpler methods have been developed that are provably secure against all but a brute force cryptanalytic attack. U.S. Pat. No. 5,583,939 ("the '939 patent") describes an exchange protocol in which a sender selects a first and a second quantity, sends one of the quantities to the receiver, e.g. the first quantity, and keeps the other, quantity, e.g. the second quantity, secret. The sender then uses a first function on the selected quantities to compute a third quantity which he also sends to the receiver. After receiving the third quantity, the receiver then selects a fourth secret quantity, and together with the first received quantity, e.g. the first quantity selected by the sender, uses a second function to calculate a fifth quantity which the receiver returns to the sender. Both the sender and the receiver now use a third and fourth function, respectively, to calculate the cryptographic key. The method disclosed in the '939 patent requires that the four functions utilized possess no inverse. That is, the four functions must possess the property that knowing one of the quantities used in calculating a quantity and the quantity thus calculated quantity, it is impossible to compute the other quantity used in performing the calculation. While the method disclosed in the '939 patent is swifter and simpler than previous methods, it requires transmitting at least two quantities from the sender to the receiver.